The present invention relates generally to multiprocessor systems and, more particularly, to systems and techniques for efficiently allocating communication bandwidth among nodes in such systems using a ringlet-type interconnect.
As the performance demands on personal computers continue to increase at a meteoric pace, processors have been developed which operate at higher and higher clock speeds. The instruction sets used to control these processors have been pared down (e.g., RISC architecture) to make them more efficient. Processor improvements alone, however, are insufficient to provide the greater bandwidth required by computer users. The other computer subsystems which support the processor, e.g., interconnects, I/O devices and memory devices, must also be designed to operate at higher speeds and support greater bandwidth. In addition to improved performance, cost has always been an issue with computer users. Thus, system designers are faced with the dual challenges of improving performance while remaining competitive on a cost basis.
Early personal computers typically included a central processing unit (CPU), some type of memory and one or more input/output (I/O) devices. These elements were interconnected to share information using what is commonly referred to as a "bus". Physically, buses are fabricated as a common set of wires to which inputs and outputs of several devices are directly connected.
Buses convey data and instructions between the elements of a digital computer. Local buses provide data transmission capability within a device, whereas system buses interconnect devices, such as I/O subsystems, memory subsystems and a central processor, together. In many systems, several devices compete for use of the system bus. In industry parlance, devices which can control the system bus are termed bus masters, while other devices, which are passive and respond to requests from the bus masters, are termed slaves. Some devices may operate at different times either as a slave or a bus master to accomplish different objectives.
In order to avoid bus contention, i.e., the situation where two bus masters have simultaneous control over the system bus, a bus arbiter can be provided to prioritize requests to use the bus. In such systems, a device which wishes to become a bus master will send a bus request signal to the arbiter over a dedicated line in the control bus. If the arbiter grants the bus request, then an acknowledgement or granting signal is transmitted back to the requesting device over another control line. The methodology by which the arbiter prioritizes requests is called the bus arbitration protocol. These protocols can be implemented as an ordered list of bus masters (i.e., the highest requesting bus master on the list receives a bus grant) or as state machines inside the arbiter.
The advent of multiprocessor architectures for personal computers is a recent trend in the design of these systems, intended to satisfy consumers' demand for ever faster and more powerful personal computers. In a typical multiprocessor computer system each of the processors may share one or more resources. Note, for example, the multiprocessor system depicted in FIG. 1. Therein, an exemplary multiprocessor system 5 is illustrated having seven nodes including a first CPU 10, a bridge 12 for connecting the system 5 to some other computer system 13, first and second memory devices 14 and 16, a frame buffer 18 for supplying information to a monitor, a direct memory access (DMA) device 20 for supplying information to a storage device or a network and a second CPU 22 having an SRAM device 24 connected thereto. According to the conventional paradigm, these nodes would be interconnected by a bus 26. Caches can be provided as shown to isolate some of the devices from the bus and to merge plural, small bus accesses into larger, cache-line sized accesses.
As multiprocessor systems grow more complex, i.e., are designed with more and more nodes, adapting the bus-type interconnect to handle the increased complexity becomes problematic. For example, capacitive loading associated with the conductive traces on the motherboard which form the bus becomes a limiting factor with respect to the speed at which the bus can be driven. Thus, an alternative interconnect architecture is desirable.
One type of proposed interconnect architecture for multiprocessor personal computer systems replaces the bus with a plurality of unidirectional point-to-point links and uses packet data techniques to transfer information. FIGS. 2(a) and 2(b) conceptualize the difference. Ringlets overcome the aforementioned drawback of conventional bus-type interconnects since their individual links can be clocked at high speeds regardless of the total number of nodes which are linked together. FIG. 2(a) depicts four of the nodes from FIG. 1 interconnected via a conventional bus. FIG. 2(b) illustrates the same four nodes interconnected via unidirectional point-to-point links 30, 32, 34 and 36. These links can be used to provide bus-like functionality by connecting the links into a ring (which structure is sometimes referred to herein as a "ringlet") and having each node pass-through packets addressed to other nodes. As will be appreciated by those skilled in the art, packets are formatted to include payload data as well as various overhead information including, for example, information associated with the target and source nodes' addresses. An exemplary packet format is illustrated in FIG. 2(c). Therein, the packet includes a target node identification field (Target ID), an old bit field, a command field, a source node identification field (Source ID), as well as payload data and, potentially, other fields including error detection, e.g., cyclic redundancy check (CRC) fields. Between the data packets, the system circulates filler data referred to herein as out-of-band information or idle symbols.
Like bus-type interconnect architectures, ringlets also require arbitration schemes to handle the eventuality of heavy loading and the prioritization of packets transmitted by the various nodes. For example, certain types of information may be guaranteed a predetermined amount of bandwidth, e.g., information used to generate audio and video output, regardless of the loading placed on the ringlet by the other tasks being performed by the processors. This type of information is referred to herein as "isochronous data", whose servicing may require a temporary restructuring of packet data transmission priorities. Moreover, if a node becomes blocked, i.e., is unable to transmit a packet of its own because its bypass queue is full of packets that it has received from another node and is supposed to pass on, then some technique is necessary to command the other nodes to stop sending packets until the node becomes unblocked.
Unlike bus-type interconnects where arbitration signals can be sent on dedicated signal lines, ringlets may send out-of-band control information as part of the idle symbols transmitted over the links. One example of this type of arbitration is found in the industry standard referred to as Scalable Coherent Interface (SCI), which standard is described in IEEE Publication Std 1596-1992. According to this standard, "go" bits are circulated in the ringlet as a sort of replicatable/mergeable token. A node may transmit a packet only if it has received a "go" bit as part of the out-of-band information received in an incoming packet, which "go" bit is replicated and forwarded in addition to the transmitted packet. When the need arises to throttle one or more nodes so that a blocked node can transmit a packet, the blocked node merges incoming "go" bits so that "go" bit propagation stops, which in turn precludes other nodes from transmitting packets.
This approach has several potential drawbacks. First, the "go" bits may be lost due to transmission errors, which in turn would prevent nodes from transmitting packets and reduce throughput. Second, after arbitration is resolved, "normal" packet transmission on the ringlet needs to be restarted by circulating "go" bits to the various nodes. This increases latency since "go" bit replication rates have to be constrained to provide adequate arbitration response time. I
Another type of ringlet arbitration has been described in early drafts of a proposed IEEE Standard entitled "SerialExpress--A Scalable Gigabit Extension to Serial Bus". Therein, instead of "go" bits being circulated to permit nodes to transmit packets, a blocked node sends a stop indication having a six bit node identifier. Each node in the ringlet that receives this stop indication stops sending packets and passes the stop indicator on until it is received again by the originating node, which can then transmit packets.
Like the "go" bits in the first described approach, this solution is also susceptible to transmission errors which may alter the node identifier associated with the stop indicator. Special circuitry is then needed to identify and remove aberrant stop indicators which would otherwise circulate endlessly in the ringlet. Another problem associated with the arbitration proposed in the SerialExpress standard is handling of the post-arbitration recovery phase which relies on the propagation of a special "start-now" token. This token may be difficult to reliably maintain through elasticity buffers associated with the nodes which selectively delete passing-through idle symbols.
Accordingly, it would be desirable to have a more efficient arbitration scheme for ringlet-type interconnects associated with, for example, multiprocessor personal computer systems.